#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include "./uthdrs/uthash.h"

typedef struct {
    int key;
    int val;
    UT_hash_handle hh;
}S_UTH_ITEM;


S_UTH_ITEM *g_uthash_tbl = NULL;

void UTH_Add(int key, int val);
void UTH_Del(int key);
int UTH_Find(int key, int *val);

int UTH_Find(int key, int *val){
    S_UTH_ITEM *out = NULL;
    HASH_FIND(hh, g_uthash_tbl, &key, sizeof(int), out);
    if(out != NULL){
        *val = out->val;
        return 0;
    }

    return 1;

}

void UTH_Add(int key, int val){
    S_UTH_ITEM *out = NULL;
    HASH_FIND(hh, g_uthash_tbl, &key, sizeof(int), out);
    if(out != NULL){
        HASH_DELETE(hh, g_uthash_tbl, out);
        free(out);
    }
    S_UTH_ITEM *insert = (S_UTH_ITEM *)malloc(sizeof(S_UTH_ITEM));
    memset(insert, 0, sizeof(S_UTH_ITEM));
    insert->key = key;
    insert->val = val;

    HASH_ADD(hh, g_uthash_tbl, key, sizeof(key), insert);
}


void UTH_Del(int key){
    S_UTH_ITEM *out = NULL;
    HASH_FIND(hh, g_uthash_tbl, &key, sizeof(int), out);
    if(out != NULL){
        printf("del key[%d] val[%d]\n", out->key, out->val);
        HASH_DELETE(hh, g_uthash_tbl, out);
        free(out);
    }
}


void UTH_Destroy(){
    S_UTH_ITEM *tmp = NULL;
    S_UTH_ITEM *el = NULL;
    HASH_ITER(hh, g_uthash_tbl, el, tmp) {
        printf("del key[%d] val[%d]\n", el->key, el->val);
        HASH_DELETE(hh, g_uthash_tbl, el);
        free(el);
    }
}

/*
 *  x + y = target
 *  map[target - x] = idx(x)
 *
 *  for i in [1..n]:
 *      if map[val(i)] is true:
 *          return map[val(i)], i
 *
 *  return -1, -1
 *
 *
 * */


/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* twoSum(int* numbers, int numbersSize, int target, int* returnSize){

    int i = 0;
    int cur = 0;
    int val = 0;
    int ret = 0;


    int *res = (int *)malloc(sizeof(int) * 2);
    memset(res, -1, sizeof(int)*2);
    *returnSize = 2;

    for (i=0;i<numbersSize;i++){
        cur = numbers[i];
        ret = UTH_Find(cur, &val);
        if (ret == 0) {
            res[0] = val+1;
            res[1] = i+1;
            UTH_Destroy();
            return res; // success
        }
        UTH_Add(target-cur, i);
    }
    UTH_Destroy();
    return res;
}


void do_test(){
    printf("test lc0167\n");



    int *res = NULL;

    int numbers[4] = {2, 7, 11, 15};
    int numbersSize = 4;
    int target = 18;
    int returnSize = 0;

    res = twoSum(numbers, numbersSize, target, &returnSize);
    printf("get res: res{%d, %d}, size[%d]\n", res[0], res[1], returnSize);
    free(res);
}
